#include "binomial.h"
#include "fatal.h"

/* START: fig6_52.txt */
typedef struct BinNode *Position;

struct BinNode {
	ElementType Element;
	Position LeftChild;
	Position NextSibling;
};

struct Collection {
	int CurrentSize;
	BinTree TheTrees[MaxTrees];
};

BinQueue Initialize(void) {
	BinQueue H;
	int i;

	H = malloc(sizeof(struct Collection));
	if (H == NULL)
		FatalError("Out of space!!!");
	H->CurrentSize = 0;
	for (i = 0; i < MaxTrees; i++)
		H->TheTrees[i] = NULL;
	return H;
}

static void DestroyTree(BinTree T) {
	if (T != NULL) {
		DestroyTree(T->LeftChild);
		DestroyTree(T->NextSibling);
		free(T);
	}
}

void Destroy(BinQueue H) {
	int i;

	for (i = 0; i < MaxTrees; i++)
		DestroyTree(H->TheTrees[i]);
}

BinQueue MakeEmpty(BinQueue H) {
	int i;

	Destroy(H);
	for (i = 0; i < MaxTrees; i++)
		H->TheTrees[i] = NULL;
	H->CurrentSize = 0;

	return H;
}

/* Not optimized for O(1) amortized performance */
BinQueue Insert(ElementType Item, BinQueue H) {
	BinTree NewNode;
	BinQueue OneItem;

	NewNode = malloc(sizeof(struct BinNode));
	if (NewNode == NULL)
		FatalError("Out of space!!!");
	NewNode->LeftChild = NewNode->NextSibling = NULL;
	NewNode->Element = Item;

	OneItem = Initialize();
	OneItem->CurrentSize = 1;
	OneItem->TheTrees[0] = NewNode;

	return Merge(H, OneItem);
}

/* START: fig6_56.txt */
ElementType DeleteMin(BinQueue H) {
	int i, j;
	int MinTree; /* The tree with the minimum item */
	BinQueue DeletedQueue;
	Position DeletedTree, OldRoot;
	ElementType MinItem;

	if (IsEmpty(H)) {
		Error("Empty binomial queue");
		return -Infinity;
	}

	MinItem = Infinity;
	for (i = 0; i < MaxTrees; i++) {
		if (H->TheTrees[i] && H->TheTrees[i]->Element < MinItem) {
			/* Update minimum */
			MinItem = H->TheTrees[i]->Element;
			MinTree = i;
		}
	}

	DeletedTree = H->TheTrees[MinTree];
	OldRoot = DeletedTree;
	DeletedTree = DeletedTree->LeftChild;
	free(OldRoot);

	DeletedQueue = Initialize();
	DeletedQueue->CurrentSize = (1 << MinTree) - 1;
	for (j = MinTree - 1; j >= 0; j--) {
		DeletedQueue->TheTrees[j] = DeletedTree;
		DeletedTree = DeletedTree->NextSibling;
		DeletedQueue->TheTrees[j]->NextSibling = NULL;
	}

	H->TheTrees[MinTree] = NULL;
	H->CurrentSize -= DeletedQueue->CurrentSize + 1;

	Merge(H, DeletedQueue);
	return MinItem;
}
/* END */

ElementType FindMin(BinQueue H) {
	int i;
	ElementType MinItem;

	if (IsEmpty(H)) {
		Error("Empty binomial queue");
		return 0;
	}

	MinItem = Infinity;
	for (i = 0; i < MaxTrees; i++) {
		if (H->TheTrees[i] && H->TheTrees[i]->Element < MinItem)
			MinItem = H->TheTrees[i]->Element;
	}

	return MinItem;
}

int IsEmpty(BinQueue H) {
	return H->CurrentSize == 0;
}

int IsFull(BinQueue H) {
	return H->CurrentSize == Capacity;
}

/* START: fig6_54.txt */
/* Return the result of merging equal-sized T1 and T2 */
BinTree CombineTrees(BinTree T1, BinTree T2) {
	if (T1->Element > T2->Element)
		return CombineTrees(T2, T1);
	T2->NextSibling = T1->LeftChild;
	T1->LeftChild = T2;
	return T1;
}
/* END */

/* START: fig6_55.txt */
/* Merge two binomial queues */
/* Not optimized for early termination */
/* H1 contains merged result */

BinQueue Merge(BinQueue H1, BinQueue H2) {
	BinTree T1, T2, Carry = NULL;
	int i, j;

	if (H1->CurrentSize + H2->CurrentSize > Capacity)
		Error("Merge would exceed capacity");

	H1->CurrentSize += H2->CurrentSize;
	for (i = 0, j = 1; j <= H1->CurrentSize; i++, j *= 2) {
		T1 = H1->TheTrees[i];
		T2 = H2->TheTrees[i];

		switch (!!T1 + 2 * !!T2 + 4 * !!Carry) {
		case 0: /* No trees */
		case 1: /* Only H1 */
			break;
		case 2: /* Only H2 */
			H1->TheTrees[i] = T2;
			H2->TheTrees[i] = NULL;
			break;
		case 4: /* Only Carry */
			H1->TheTrees[i] = Carry;
			Carry = NULL;
			break;
		case 3: /* H1 and H2 */
			Carry = CombineTrees(T1, T2);
			H1->TheTrees[i] = H2->TheTrees[i] = NULL;
			break;
		case 5: /* H1 and Carry */
			Carry = CombineTrees(T1, Carry);
			H1->TheTrees[i] = NULL;
			break;
		case 6: /* H2 and Carry */
			Carry = CombineTrees(T2, Carry);
			H2->TheTrees[i] = NULL;
			break;
		case 7: /* All three */
			H1->TheTrees[i] = Carry;
			Carry = CombineTrees(T1, T2);
			H2->TheTrees[i] = NULL;
			break;
		}
	}
	return H1;
}
/* END */
